home *** CD-ROM | disk | FTP | other *** search
/ PC/CD Gamer UK 120 / CD Gamer Issue 120 (March 2003) (Disc 2).ISO / mods / Q2_Codered / codeRED1_0.exe / Data1.cab / cmodel.c < prev    next >
Encoding:
C/C++ Source or Header  |  2002-08-13  |  36.9 KB  |  1,771 lines
  1. /*
  2. Copyright (C) 1997-2001 Id Software, Inc.
  3.  
  4. This program is free software; you can redistribute it and/or
  5. modify it under the terms of the GNU General Public License
  6. as published by the Free Software Foundation; either version 2
  7. of the License, or (at your option) any later version.
  8.  
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
  12.  
  13. See the GNU General Public License for more details.
  14.  
  15. You should have received a copy of the GNU General Public License
  16. along with this program; if not, write to the Free Software
  17. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18.  
  19. */
  20. // cmodel.c -- model loading
  21.  
  22. #include "qcommon.h"
  23.  
  24. typedef struct
  25. {
  26.     cplane_t    *plane;
  27.     int            children[2];        // negative numbers are leafs
  28. } cnode_t;
  29.  
  30. typedef struct
  31. {
  32.     cplane_t    *plane;
  33.     mapsurface_t    *surface;
  34. } cbrushside_t;
  35.  
  36. typedef struct
  37. {
  38.     int            contents;
  39.     int            cluster;
  40.     int            area;
  41.     unsigned short    firstleafbrush;
  42.     unsigned short    numleafbrushes;
  43. } cleaf_t;
  44.  
  45. typedef struct
  46. {
  47.     int            contents;
  48.     int            numsides;
  49.     int            firstbrushside;
  50.     int            checkcount;        // to avoid repeated testings
  51. } cbrush_t;
  52.  
  53. typedef struct
  54. {
  55.     int        numareaportals;
  56.     int        firstareaportal;
  57.     int        floodnum;            // if two areas have equal floodnums, they are connected
  58.     int        floodvalid;
  59. } carea_t;
  60.  
  61. int            checkcount;
  62.  
  63. char        map_name[MAX_QPATH];
  64.  
  65. int            numbrushsides;
  66. cbrushside_t map_brushsides[MAX_MAP_BRUSHSIDES];
  67.  
  68. int            numtexinfo;
  69. mapsurface_t    map_surfaces[MAX_MAP_TEXINFO];
  70.  
  71. int            numplanes;
  72. cplane_t    map_planes[MAX_MAP_PLANES+6];        // extra for box hull
  73.  
  74. int            numnodes;
  75. cnode_t        map_nodes[MAX_MAP_NODES+6];        // extra for box hull
  76.  
  77. int            numleafs = 1;    // allow leaf funcs to be called without a map
  78. cleaf_t        map_leafs[MAX_MAP_LEAFS];
  79. int            emptyleaf, solidleaf;
  80.  
  81. int            numleafbrushes;
  82. unsigned short    map_leafbrushes[MAX_MAP_LEAFBRUSHES];
  83.  
  84. int            numcmodels;
  85. cmodel_t    map_cmodels[MAX_MAP_MODELS];
  86.  
  87. int            numbrushes;
  88. cbrush_t    map_brushes[MAX_MAP_BRUSHES];
  89.  
  90. int            numvisibility;
  91. byte        map_visibility[MAX_MAP_VISIBILITY];
  92. dvis_t        *map_vis = (dvis_t *)map_visibility;
  93.  
  94. int            numentitychars;
  95. char        map_entitystring[MAX_MAP_ENTSTRING];
  96.  
  97. int            numareas = 1;
  98. carea_t        map_areas[MAX_MAP_AREAS];
  99.  
  100. int            numareaportals;
  101. dareaportal_t map_areaportals[MAX_MAP_AREAPORTALS];
  102.  
  103. int            numclusters = 1;
  104.  
  105. mapsurface_t    nullsurface;
  106.  
  107. int            floodvalid;
  108.  
  109. qboolean    portalopen[MAX_MAP_AREAPORTALS];
  110.  
  111.  
  112. cvar_t        *map_noareas;
  113.  
  114. void    CM_InitBoxHull (void);
  115. void    FloodAreaConnections (void);
  116.  
  117.  
  118. int        c_pointcontents;
  119. int        c_traces, c_brush_traces;
  120.  
  121.  
  122. /*
  123. ===============================================================================
  124.  
  125.                     MAP LOADING
  126.  
  127. ===============================================================================
  128. */
  129.  
  130. byte    *cmod_base;
  131.  
  132. /*
  133. =================
  134. CMod_LoadSubmodels
  135. =================
  136. */
  137. void CMod_LoadSubmodels (lump_t *l)
  138. {
  139.     dmodel_t    *in;
  140.     cmodel_t    *out;
  141.     int            i, j, count;
  142.  
  143.     in = (void *)(cmod_base + l->fileofs);
  144.     if (l->filelen % sizeof(*in))
  145.         Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
  146.     count = l->filelen / sizeof(*in);
  147.  
  148.     if (count < 1)
  149.         Com_Error (ERR_DROP, "Map with no models");
  150.     if (count > MAX_MAP_MODELS)
  151.         Com_Error (ERR_DROP, "Map has too many models");
  152.  
  153.     numcmodels = count;
  154.  
  155.     for ( i=0 ; i<count ; i++, in++, out++)
  156.     {
  157.         out = &map_cmodels[i];
  158.  
  159.         for (j=0 ; j<3 ; j++)
  160.         {    // spread the mins / maxs by a pixel
  161.             out->mins[j] = LittleFloat (in->mins[j]) - 1;
  162.             out->maxs[j] = LittleFloat (in->maxs[j]) + 1;
  163.             out->origin[j] = LittleFloat (in->origin[j]);
  164.         }
  165.         out->headnode = LittleLong (in->headnode);
  166.     }
  167. }
  168.  
  169.  
  170. /*
  171. =================
  172. CMod_LoadSurfaces
  173. =================
  174. */
  175. void CMod_LoadSurfaces (lump_t *l)
  176. {
  177.     texinfo_t    *in;
  178.     mapsurface_t    *out;
  179.     int            i, count;
  180.  
  181.     in = (void *)(cmod_base + l->fileofs);
  182.     if (l->filelen % sizeof(*in))
  183.         Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
  184.     count = l->filelen / sizeof(*in);
  185.     if (count < 1)
  186.         Com_Error (ERR_DROP, "Map with no surfaces");
  187.     if (count > MAX_MAP_TEXINFO)
  188.         Com_Error (ERR_DROP, "Map has too many surfaces");
  189.  
  190.     numtexinfo = count;
  191.     out = map_surfaces;
  192.  
  193.     for ( i=0 ; i<count ; i++, in++, out++)
  194.     {
  195.         strncpy (out->c.name, in->texture, sizeof(out->c.name)-1);
  196.         strncpy (out->rname, in->texture, sizeof(out->rname)-1);
  197.         out->c.flags = LittleLong (in->flags);
  198.         out->c.value = LittleLong (in->value);
  199.     }
  200. }
  201.  
  202.  
  203. /*
  204. =================
  205. CMod_LoadNodes
  206.  
  207. =================
  208. */
  209. void CMod_LoadNodes (lump_t *l)
  210. {
  211.     dnode_t        *in;
  212.     int            child;
  213.     cnode_t        *out;
  214.     int            i, j, count;
  215.     
  216.     in = (void *)(cmod_base + l->fileofs);
  217.     if (l->filelen % sizeof(*in))
  218.         Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
  219.     count = l->filelen / sizeof(*in);
  220.  
  221.     if (count < 1)
  222.         Com_Error (ERR_DROP, "Map has no nodes");
  223.     if (count > MAX_MAP_NODES)
  224.         Com_Error (ERR_DROP, "Map has too many nodes");
  225.  
  226.     out = map_nodes;
  227.  
  228.     numnodes = count;
  229.  
  230.     for (i=0 ; i<count ; i++, out++, in++)
  231.     {
  232.         out->plane = map_planes + LittleLong(in->planenum);
  233.         for (j=0 ; j<2 ; j++)
  234.         {
  235.             child = LittleLong (in->children[j]);
  236.             out->children[j] = child;
  237.         }
  238.     }
  239.  
  240. }
  241.  
  242. /*
  243. =================
  244. CMod_LoadBrushes
  245.  
  246. =================
  247. */
  248. void CMod_LoadBrushes (lump_t *l)
  249. {
  250.     dbrush_t    *in;
  251.     cbrush_t    *out;
  252.     int            i, count;
  253.     
  254.     in = (void *)(cmod_base + l->fileofs);
  255.     if (l->filelen % sizeof(*in))
  256.         Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
  257.     count = l->filelen / sizeof(*in);
  258.  
  259.     if (count > MAX_MAP_BRUSHES)
  260.         Com_Error (ERR_DROP, "Map has too many brushes");
  261.  
  262.     out = map_brushes;
  263.  
  264.     numbrushes = count;
  265.  
  266.     for (i=0 ; i<count ; i++, out++, in++)
  267.     {
  268.         out->firstbrushside = LittleLong(in->firstside);
  269.         out->numsides = LittleLong(in->numsides);
  270.         out->contents = LittleLong(in->contents);
  271.     }
  272.  
  273. }
  274.  
  275. /*
  276. =================
  277. CMod_LoadLeafs
  278. =================
  279. */
  280. void CMod_LoadLeafs (lump_t *l)
  281. {
  282.     int            i;
  283.     cleaf_t        *out;
  284.     dleaf_t     *in;
  285.     int            count;
  286.     
  287.     in = (void *)(cmod_base + l->fileofs);
  288.     if (l->filelen % sizeof(*in))
  289.         Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
  290.     count = l->filelen / sizeof(*in);
  291.  
  292.     if (count < 1)
  293.         Com_Error (ERR_DROP, "Map with no leafs");
  294.     // need to save space for box planes
  295.     if (count > MAX_MAP_PLANES)
  296.         Com_Error (ERR_DROP, "Map has too many planes");
  297.  
  298.     out = map_leafs;    
  299.     numleafs = count;
  300.     numclusters = 0;
  301.  
  302.     for ( i=0 ; i<count ; i++, in++, out++)
  303.     {
  304.         out->contents = LittleLong (in->contents);
  305.         out->cluster = LittleShort (in->cluster);
  306.         out->area = LittleShort (in->area);
  307.         out->firstleafbrush = LittleShort (in->firstleafbrush);
  308.         out->numleafbrushes = LittleShort (in->numleafbrushes);
  309.  
  310.         if (out->cluster >= numclusters)
  311.             numclusters = out->cluster + 1;
  312.     }
  313.  
  314.     if (map_leafs[0].contents != CONTENTS_SOLID)
  315.         Com_Error (ERR_DROP, "Map leaf 0 is not CONTENTS_SOLID");
  316.     solidleaf = 0;
  317.     emptyleaf = -1;
  318.     for (i=1 ; i<numleafs ; i++)
  319.     {
  320.         if (!map_leafs[i].contents)
  321.         {
  322.             emptyleaf = i;
  323.             break;
  324.         }
  325.     }
  326.     if (emptyleaf == -1)
  327.         Com_Error (ERR_DROP, "Map does not have an empty leaf");
  328. }
  329.  
  330. /*
  331. =================
  332. CMod_LoadPlanes
  333. =================
  334. */
  335. void CMod_LoadPlanes (lump_t *l)
  336. {
  337.     int            i, j;
  338.     cplane_t    *out;
  339.     dplane_t     *in;
  340.     int            count;
  341.     int            bits;
  342.     
  343.     in = (void *)(cmod_base + l->fileofs);
  344.     if (l->filelen % sizeof(*in))
  345.         Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
  346.     count = l->filelen / sizeof(*in);
  347.  
  348.     if (count < 1)
  349.         Com_Error (ERR_DROP, "Map with no planes");
  350.     // need to save space for box planes
  351.     if (count > MAX_MAP_PLANES)
  352.         Com_Error (ERR_DROP, "Map has too many planes");
  353.  
  354.     out = map_planes;    
  355.     numplanes = count;
  356.  
  357.     for ( i=0 ; i<count ; i++, in++, out++)
  358.     {
  359.         bits = 0;
  360.         for (j=0 ; j<3 ; j++)
  361.         {
  362.             out->normal[j] = LittleFloat (in->normal[j]);
  363.             if (out->normal[j] < 0)
  364.                 bits |= 1<<j;
  365.         }
  366.  
  367.         out->dist = LittleFloat (in->dist);
  368.         out->type = LittleLong (in->type);
  369.         out->signbits = bits;
  370.     }
  371. }
  372.  
  373. /*
  374. =================
  375. CMod_LoadLeafBrushes
  376. =================
  377. */
  378. void CMod_LoadLeafBrushes (lump_t *l)
  379. {
  380.     int            i;
  381.     unsigned short    *out;
  382.     unsigned short     *in;
  383.     int            count;
  384.     
  385.     in = (void *)(cmod_base + l->fileofs);
  386.     if (l->filelen % sizeof(*in))
  387.         Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
  388.     count = l->filelen / sizeof(*in);
  389.  
  390.     if (count < 1)
  391.         Com_Error (ERR_DROP, "Map with no planes");
  392.     // need to save space for box planes
  393.     if (count > MAX_MAP_LEAFBRUSHES)
  394.         Com_Error (ERR_DROP, "Map has too many leafbrushes");
  395.  
  396.     out = map_leafbrushes;
  397.     numleafbrushes = count;
  398.  
  399.     for ( i=0 ; i<count ; i++, in++, out++)
  400.         *out = LittleShort (*in);
  401. }
  402.  
  403. /*
  404. =================
  405. CMod_LoadBrushSides
  406. =================
  407. */
  408. void CMod_LoadBrushSides (lump_t *l)
  409. {
  410.     int            i, j;
  411.     cbrushside_t    *out;
  412.     dbrushside_t     *in;
  413.     int            count;
  414.     int            num;
  415.  
  416.     in = (void *)(cmod_base + l->fileofs);
  417.     if (l->filelen % sizeof(*in))
  418.         Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
  419.     count = l->filelen / sizeof(*in);
  420.  
  421.     // need to save space for box planes
  422.     if (count > MAX_MAP_BRUSHSIDES)
  423.         Com_Error (ERR_DROP, "Map has too many planes");
  424.  
  425.     out = map_brushsides;    
  426.     numbrushsides = count;
  427.  
  428.     for ( i=0 ; i<count ; i++, in++, out++)
  429.     {
  430.         num = LittleShort (in->planenum);
  431.         out->plane = &map_planes[num];
  432.         j = LittleShort (in->texinfo);
  433.         if (j >= numtexinfo)
  434.             Com_Error (ERR_DROP, "Bad brushside texinfo");
  435.         out->surface = &map_surfaces[j];
  436.     }
  437. }
  438.  
  439. /*
  440. =================
  441. CMod_LoadAreas
  442. =================
  443. */
  444. void CMod_LoadAreas (lump_t *l)
  445. {
  446.     int            i;
  447.     carea_t        *out;
  448.     darea_t     *in;
  449.     int            count;
  450.  
  451.     in = (void *)(cmod_base + l->fileofs);
  452.     if (l->filelen % sizeof(*in))
  453.         Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
  454.     count = l->filelen / sizeof(*in);
  455.  
  456.     if (count > MAX_MAP_AREAS)
  457.         Com_Error (ERR_DROP, "Map has too many areas");
  458.  
  459.     out = map_areas;
  460.     numareas = count;
  461.  
  462.     for ( i=0 ; i<count ; i++, in++, out++)
  463.     {
  464.         out->numareaportals = LittleLong (in->numareaportals);
  465.         out->firstareaportal = LittleLong (in->firstareaportal);
  466.         out->floodvalid = 0;
  467.         out->floodnum = 0;
  468.     }
  469. }
  470.  
  471. /*
  472. =================
  473. CMod_LoadAreaPortals
  474. =================
  475. */
  476. void CMod_LoadAreaPortals (lump_t *l)
  477. {
  478.     int            i;
  479.     dareaportal_t        *out;
  480.     dareaportal_t     *in;
  481.     int            count;
  482.  
  483.     in = (void *)(cmod_base + l->fileofs);
  484.     if (l->filelen % sizeof(*in))
  485.         Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
  486.     count = l->filelen / sizeof(*in);
  487.  
  488.     if (count > MAX_MAP_AREAS)
  489.         Com_Error (ERR_DROP, "Map has too many areas");
  490.  
  491.     out = map_areaportals;
  492.     numareaportals = count;
  493.  
  494.     for ( i=0 ; i<count ; i++, in++, out++)
  495.     {
  496.         out->portalnum = LittleLong (in->portalnum);
  497.         out->otherarea = LittleLong (in->otherarea);
  498.     }
  499. }
  500.  
  501. /*
  502. =================
  503. CMod_LoadVisibility
  504. =================
  505. */
  506. void CMod_LoadVisibility (lump_t *l)
  507. {
  508.     int        i;
  509.  
  510.     numvisibility = l->filelen;
  511.     if (l->filelen > MAX_MAP_VISIBILITY)
  512.         Com_Error (ERR_DROP, "Map has too large visibility lump");
  513.  
  514.     memcpy (map_visibility, cmod_base + l->fileofs, l->filelen);
  515.  
  516.     map_vis->numclusters = LittleLong (map_vis->numclusters);
  517.     for (i=0 ; i<map_vis->numclusters ; i++)
  518.     {
  519.         map_vis->bitofs[i][0] = LittleLong (map_vis->bitofs[i][0]);
  520.         map_vis->bitofs[i][1] = LittleLong (map_vis->bitofs[i][1]);
  521.     }
  522. }
  523.  
  524.  
  525. /*
  526. =================
  527. CMod_LoadEntityString
  528. =================
  529. */
  530. void CMod_LoadEntityString (lump_t *l)
  531. {
  532.     numentitychars = l->filelen;
  533.     if (l->filelen > MAX_MAP_ENTSTRING)
  534.         Com_Error (ERR_DROP, "Map has too large entity lump");
  535.  
  536.     memcpy (map_entitystring, cmod_base + l->fileofs, l->filelen);
  537. }
  538.  
  539.  
  540.  
  541. /*
  542. ==================
  543. CM_LoadMap
  544.  
  545. Loads in the map and all submodels
  546. ==================
  547. */
  548. cmodel_t *CM_LoadMap (char *name, qboolean clientload, unsigned *checksum)
  549. {
  550.     unsigned        *buf;
  551.     int                i;
  552.     dheader_t        header;
  553.     int                length;
  554.     static unsigned    last_checksum;
  555.  
  556.     map_noareas = Cvar_Get ("map_noareas", "0", 0);
  557.  
  558.     if (  !strcmp (map_name, name) && (clientload || !Cvar_VariableValue ("flushmap")) )
  559.     {
  560.         *checksum = last_checksum;
  561.         if (!clientload)
  562.         {
  563.             memset (portalopen, 0, sizeof(portalopen));
  564.             FloodAreaConnections ();
  565.         }
  566.         return &map_cmodels[0];        // still have the right version
  567.     }
  568.  
  569.     // free old stuff
  570.     numplanes = 0;
  571.     numnodes = 0;
  572.     numleafs = 0;
  573.     numcmodels = 0;
  574.     numvisibility = 0;
  575.     numentitychars = 0;
  576.     map_entitystring[0] = 0;
  577.     map_name[0] = 0;
  578.  
  579.     if (!name || !name[0])
  580.     {
  581.         numleafs = 1;
  582.         numclusters = 1;
  583.         numareas = 1;
  584.         *checksum = 0;
  585.         return &map_cmodels[0];            // cinematic servers won't have anything at all
  586.     }
  587.  
  588.     //
  589.     // load the file
  590.     //
  591.     length = FS_LoadFile (name, (void **)&buf);
  592.     if (!buf)
  593.         Com_Error (ERR_DROP, "Couldn't load %s", name);
  594.  
  595.     last_checksum = LittleLong (Com_BlockChecksum (buf, length));
  596.     *checksum = last_checksum;
  597.  
  598.     header = *(dheader_t *)buf;
  599.     for (i=0 ; i<sizeof(dheader_t)/4 ; i++)
  600.         ((int *)&header)[i] = LittleLong ( ((int *)&header)[i]);
  601.  
  602.     if (header.version != BSPVERSION)
  603.         Com_Error (ERR_DROP, "CMod_LoadBrushModel: %s has wrong version number (%i should be %i)"
  604.         , name, header.version, BSPVERSION);
  605.  
  606.     cmod_base = (byte *)buf;
  607.  
  608.     // load into heap
  609.     CMod_LoadSurfaces (&header.lumps[LUMP_TEXINFO]);
  610.     CMod_LoadLeafs (&header.lumps[LUMP_LEAFS]);
  611.     CMod_LoadLeafBrushes (&header.lumps[LUMP_LEAFBRUSHES]);
  612.     CMod_LoadPlanes (&header.lumps[LUMP_PLANES]);
  613.     CMod_LoadBrushes (&header.lumps[LUMP_BRUSHES]);
  614.     CMod_LoadBrushSides (&header.lumps[LUMP_BRUSHSIDES]);
  615.     CMod_LoadSubmodels (&header.lumps[LUMP_MODELS]);
  616.     CMod_LoadNodes (&header.lumps[LUMP_NODES]);
  617.     CMod_LoadAreas (&header.lumps[LUMP_AREAS]);
  618.     CMod_LoadAreaPortals (&header.lumps[LUMP_AREAPORTALS]);
  619.     CMod_LoadVisibility (&header.lumps[LUMP_VISIBILITY]);
  620.     CMod_LoadEntityString (&header.lumps[LUMP_ENTITIES]);
  621.  
  622.     FS_FreeFile (buf);
  623.  
  624.     CM_InitBoxHull ();
  625.  
  626.     memset (portalopen, 0, sizeof(portalopen));
  627.     FloodAreaConnections ();
  628.  
  629.     strcpy (map_name, name);
  630.  
  631.     return &map_cmodels[0];
  632. }
  633.  
  634. /*
  635. ==================
  636. CM_InlineModel
  637. ==================
  638. */
  639. cmodel_t    *CM_InlineModel (char *name)
  640. {
  641.     int        num;
  642.  
  643.     if (!name || name[0] != '*')
  644.         Com_Error (ERR_DROP, "CM_InlineModel: bad name");
  645.     num = atoi (name+1);
  646.     if (num < 1 || num >= numcmodels)
  647.         Com_Error (ERR_DROP, "CM_InlineModel: bad number");
  648.  
  649.     return &map_cmodels[num];
  650. }
  651.  
  652. int        CM_NumClusters (void)
  653. {
  654.     return numclusters;
  655. }
  656.  
  657. int        CM_NumInlineModels (void)
  658. {
  659.     return numcmodels;
  660. }
  661.  
  662. char    *CM_EntityString (void)
  663. {
  664.     return map_entitystring;
  665. }
  666.  
  667. int        CM_LeafContents (int leafnum)
  668. {
  669.     if (leafnum < 0 || leafnum >= numleafs)
  670.         Com_Error (ERR_DROP, "CM_LeafContents: bad number");
  671.     return map_leafs[leafnum].contents;
  672. }
  673.  
  674. int        CM_LeafCluster (int leafnum)
  675. {
  676.     if (leafnum < 0 || leafnum >= numleafs)
  677.         Com_Error (ERR_DROP, "CM_LeafCluster: bad number");
  678.     return map_leafs[leafnum].cluster;
  679. }
  680.  
  681. int        CM_LeafArea (int leafnum)
  682. {
  683.     if (leafnum < 0 || leafnum >= numleafs)
  684.         Com_Error (ERR_DROP, "CM_LeafArea: bad number");
  685.     return map_leafs[leafnum].area;
  686. }
  687.  
  688. //=======================================================================
  689.  
  690.  
  691. cplane_t    *box_planes;
  692. int            box_headnode;
  693. cbrush_t    *box_brush;
  694. cleaf_t        *box_leaf;
  695.  
  696. /*
  697. ===================
  698. CM_InitBoxHull
  699.  
  700. Set up the planes and nodes so that the six floats of a bounding box
  701. can just be stored out and get a proper clipping hull structure.
  702. ===================
  703. */
  704. void CM_InitBoxHull (void)
  705. {
  706.     int            i;
  707.     int            side;
  708.     cnode_t        *c;
  709.     cplane_t    *p;
  710.     cbrushside_t    *s;
  711.  
  712.     box_headnode = numnodes;
  713.     box_planes = &map_planes[numplanes];
  714.     if (numnodes+6 > MAX_MAP_NODES
  715.         || numbrushes+1 > MAX_MAP_BRUSHES
  716.         || numleafbrushes+1 > MAX_MAP_LEAFBRUSHES
  717.         || numbrushsides+6 > MAX_MAP_BRUSHSIDES
  718.         || numplanes+12 > MAX_MAP_PLANES)
  719.         Com_Error (ERR_DROP, "Not enough room for box tree");
  720.  
  721.     box_brush = &map_brushes[numbrushes];
  722.     box_brush->numsides = 6;
  723.     box_brush->firstbrushside = numbrushsides;
  724.     box_brush->contents = CONTENTS_MONSTER;
  725.  
  726.     box_leaf = &map_leafs[numleafs];
  727.     box_leaf->contents = CONTENTS_MONSTER;
  728.     box_leaf->firstleafbrush = numleafbrushes;
  729.     box_leaf->numleafbrushes = 1;
  730.  
  731.     map_leafbrushes[numleafbrushes] = numbrushes;
  732.  
  733.     for (i=0 ; i<6 ; i++)
  734.     {
  735.         side = i&1;
  736.  
  737.         // brush sides
  738.         s = &map_brushsides[numbrushsides+i];
  739.         s->plane =     map_planes + (numplanes+i*2+side);
  740.         s->surface = &nullsurface;
  741.  
  742.         // nodes
  743.         c = &map_nodes[box_headnode+i];
  744.         c->plane = map_planes + (numplanes+i*2);
  745.         c->children[side] = -1 - emptyleaf;
  746.         if (i != 5)
  747.             c->children[side^1] = box_headnode+i + 1;
  748.         else
  749.             c->children[side^1] = -1 - numleafs;
  750.  
  751.         // planes
  752.         p = &box_planes[i*2];
  753.         p->type = i>>1;
  754.         p->signbits = 0;
  755.         VectorClear (p->normal);
  756.         p->normal[i>>1] = 1;
  757.  
  758.         p = &box_planes[i*2+1];
  759.         p->type = 3 + (i>>1);
  760.         p->signbits = 0;
  761.         VectorClear (p->normal);
  762.         p->normal[i>>1] = -1;
  763.     }    
  764. }
  765.  
  766.  
  767. /*
  768. ===================
  769. CM_HeadnodeForBox
  770.  
  771. To keep everything totally uniform, bounding boxes are turned into small
  772. BSP trees instead of being compared directly.
  773. ===================
  774. */
  775. int    CM_HeadnodeForBox (vec3_t mins, vec3_t maxs)
  776. {
  777.     box_planes[0].dist = maxs[0];
  778.     box_planes[1].dist = -maxs[0];
  779.     box_planes[2].dist = mins[0];
  780.     box_planes[3].dist = -mins[0];
  781.     box_planes[4].dist = maxs[1];
  782.     box_planes[5].dist = -maxs[1];
  783.     box_planes[6].dist = mins[1];
  784.     box_planes[7].dist = -mins[1];
  785.     box_planes[8].dist = maxs[2];
  786.     box_planes[9].dist = -maxs[2];
  787.     box_planes[10].dist = mins[2];
  788.     box_planes[11].dist = -mins[2];
  789.  
  790.     return box_headnode;
  791. }
  792.  
  793.  
  794. /*
  795. ==================
  796. CM_PointLeafnum_r
  797.  
  798. ==================
  799. */
  800. int CM_PointLeafnum_r (vec3_t p, int num)
  801. {
  802.     float        d;
  803.     cnode_t        *node;
  804.     cplane_t    *plane;
  805.  
  806.     while (num >= 0)
  807.     {
  808.         node = map_nodes + num;
  809.         plane = node->plane;
  810.         
  811.         if (plane->type < 3)
  812.             d = p[plane->type] - plane->dist;
  813.         else
  814.             d = DotProduct (plane->normal, p) - plane->dist;
  815.         if (d < 0)
  816.             num = node->children[1];
  817.         else
  818.             num = node->children[0];
  819.     }
  820.  
  821.     c_pointcontents++;        // optimize counter
  822.  
  823.     return -1 - num;
  824. }
  825.  
  826. int CM_PointLeafnum (vec3_t p)
  827. {
  828.     if (!numplanes)
  829.         return 0;        // sound may call this without map loaded
  830.     return CM_PointLeafnum_r (p, 0);
  831. }
  832.  
  833.  
  834.  
  835. /*
  836. =============
  837. CM_BoxLeafnums
  838.  
  839. Fills in a list of all the leafs touched
  840. =============
  841. */
  842. int        leaf_count, leaf_maxcount;
  843. int        *leaf_list;
  844. float    *leaf_mins, *leaf_maxs;
  845. int        leaf_topnode;
  846.  
  847. void CM_BoxLeafnums_r (int nodenum)
  848. {
  849.     cplane_t    *plane;
  850.     cnode_t        *node;
  851.     int        s;
  852.  
  853.     while (1)
  854.     {
  855.         if (nodenum < 0)
  856.         {
  857.             if (leaf_count >= leaf_maxcount)
  858.             {
  859. //                Com_Printf ("CM_BoxLeafnums_r: overflow\n");
  860.                 return;
  861.             }
  862.             leaf_list[leaf_count++] = -1 - nodenum;
  863.             return;
  864.         }
  865.     
  866.         node = &map_nodes[nodenum];
  867.         plane = node->plane;
  868. //        s = BoxOnPlaneSide (leaf_mins, leaf_maxs, plane);
  869.         s = BOX_ON_PLANE_SIDE(leaf_mins, leaf_maxs, plane);
  870.         if (s == 1)
  871.             nodenum = node->children[0];
  872.         else if (s == 2)
  873.             nodenum = node->children[1];
  874.         else
  875.         {    // go down both
  876.             if (leaf_topnode == -1)
  877.                 leaf_topnode = nodenum;
  878.             CM_BoxLeafnums_r (node->children[0]);
  879.             nodenum = node->children[1];
  880.         }
  881.  
  882.     }
  883. }
  884.  
  885. int    CM_BoxLeafnums_headnode (vec3_t mins, vec3_t maxs, int *list, int listsize, int headnode, int *topnode)
  886. {
  887.     leaf_list = list;
  888.     leaf_count = 0;
  889.     leaf_maxcount = listsize;
  890.     leaf_mins = mins;
  891.     leaf_maxs = maxs;
  892.  
  893.     leaf_topnode = -1;
  894.  
  895.     CM_BoxLeafnums_r (headnode);
  896.  
  897.     if (topnode)
  898.         *topnode = leaf_topnode;
  899.  
  900.     return leaf_count;
  901. }
  902.  
  903. int    CM_BoxLeafnums (vec3_t mins, vec3_t maxs, int *list, int listsize, int *topnode)
  904. {
  905.     return CM_BoxLeafnums_headnode (mins, maxs, list,
  906.         listsize, map_cmodels[0].headnode, topnode);
  907. }
  908.  
  909.  
  910.  
  911. /*
  912. ==================
  913. CM_PointContents
  914.  
  915. ==================
  916. */
  917. int CM_PointContents (vec3_t p, int headnode)
  918. {
  919.     int        l;
  920.  
  921.     if (!numnodes)    // map not loaded
  922.         return 0;
  923.  
  924.     l = CM_PointLeafnum_r (p, headnode);
  925.  
  926.     return map_leafs[l].contents;
  927. }
  928.  
  929. /*
  930. ==================
  931. CM_TransformedPointContents
  932.  
  933. Handles offseting and rotation of the end points for moving and
  934. rotating entities
  935. ==================
  936. */
  937. int    CM_TransformedPointContents (vec3_t p, int headnode, vec3_t origin, vec3_t angles)
  938. {
  939.     vec3_t        p_l;
  940.     vec3_t        temp;
  941.     vec3_t        forward, right, up;
  942.     int            l;
  943.  
  944.     // subtract origin offset
  945.     VectorSubtract (p, origin, p_l);
  946.  
  947.     // rotate start and end into the models frame of reference
  948.     if (headnode != box_headnode && 
  949.     (angles[0] || angles[1] || angles[2]) )
  950.     {
  951.         AngleVectors (angles, forward, right, up);
  952.  
  953.         VectorCopy (p_l, temp);
  954.         p_l[0] = DotProduct (temp, forward);
  955.         p_l[1] = -DotProduct (temp, right);
  956.         p_l[2] = DotProduct (temp, up);
  957.     }
  958.  
  959.     l = CM_PointLeafnum_r (p_l, headnode);
  960.  
  961.     return map_leafs[l].contents;
  962. }
  963.  
  964.  
  965. /*
  966. ===============================================================================
  967.  
  968. BOX TRACING
  969.  
  970. ===============================================================================
  971. */
  972.  
  973. // 1/32 epsilon to keep floating point happy
  974. #define    DIST_EPSILON    (0.03125)
  975.  
  976. vec3_t    trace_start, trace_end;
  977. vec3_t    trace_mins, trace_maxs;
  978. vec3_t    trace_extents;
  979.  
  980. trace_t    trace_trace;
  981. int        trace_contents;
  982. qboolean    trace_ispoint;        // optimized case
  983.  
  984. /*
  985. ================
  986. CM_ClipBoxToBrush
  987. ================
  988. */
  989. void CM_ClipBoxToBrush (vec3_t mins, vec3_t maxs, vec3_t p1, vec3_t p2,
  990.                       trace_t *trace, cbrush_t *brush)
  991. {
  992.     int            i, j;
  993.     cplane_t    *plane, *clipplane;
  994.     float        dist;
  995.     float        enterfrac, leavefrac;
  996.     vec3_t        ofs;
  997.     float        d1, d2;
  998.     qboolean    getout, startout;
  999.     float        f;
  1000.     cbrushside_t    *side, *leadside;
  1001.  
  1002.     enterfrac = -1;
  1003.     leavefrac = 1;
  1004.     clipplane = NULL;
  1005.  
  1006.     if (!brush->numsides)
  1007.         return;
  1008.  
  1009.     c_brush_traces++;
  1010.  
  1011.     getout = false;
  1012.     startout = false;
  1013.     leadside = NULL;
  1014.  
  1015.     for (i=0 ; i<brush->numsides ; i++)
  1016.     {
  1017.         side = &map_brushsides[brush->firstbrushside+i];
  1018.         plane = side->plane;
  1019.  
  1020.         // FIXME: special case for axial
  1021.  
  1022.         if (!trace_ispoint)
  1023.         {    // general box case
  1024.  
  1025.             // push the plane out apropriately for mins/maxs
  1026.  
  1027.             // FIXME: use signbits into 8 way lookup for each mins/maxs
  1028.             for (j=0 ; j<3 ; j++)
  1029.             {
  1030.                 if (plane->normal[j] < 0)
  1031.                     ofs[j] = maxs[j];
  1032.                 else
  1033.                     ofs[j] = mins[j];
  1034.             }
  1035.             dist = DotProduct (ofs, plane->normal);
  1036.             dist = plane->dist - dist;
  1037.         }
  1038.         else
  1039.         {    // special point case
  1040.             dist = plane->dist;
  1041.         }
  1042.  
  1043.         d1 = DotProduct (p1, plane->normal) - dist;
  1044.         d2 = DotProduct (p2, plane->normal) - dist;
  1045.  
  1046.         if (d2 > 0)
  1047.             getout = true;    // endpoint is not in solid
  1048.         if (d1 > 0)
  1049.             startout = true;
  1050.  
  1051.         // if completely in front of face, no intersection
  1052.         if (d1 > 0 && d2 >= d1)
  1053.             return;
  1054.  
  1055.         if (d1 <= 0 && d2 <= 0)
  1056.             continue;
  1057.  
  1058.         // crosses face
  1059.         if (d1 > d2)
  1060.         {    // enter
  1061.             f = (d1-DIST_EPSILON) / (d1-d2);
  1062.             if (f > enterfrac)
  1063.             {
  1064.                 enterfrac = f;
  1065.                 clipplane = plane;
  1066.                 leadside = side;
  1067.             }
  1068.         }
  1069.         else
  1070.         {    // leave
  1071.             f = (d1+DIST_EPSILON) / (d1-d2);
  1072.             if (f < leavefrac)
  1073.                 leavefrac = f;
  1074.         }
  1075.     }
  1076.  
  1077.     if (!startout)
  1078.     {    // original point was inside brush
  1079.         trace->startsolid = true;
  1080.         if (!getout)
  1081.             trace->allsolid = true;
  1082.         return;
  1083.     }
  1084.     if (enterfrac < leavefrac)
  1085.     {
  1086.         if (enterfrac > -1 && enterfrac < trace->fraction)
  1087.         {
  1088.             if (enterfrac < 0)
  1089.                 enterfrac = 0;
  1090.             trace->fraction = enterfrac;
  1091.             trace->plane = *clipplane;
  1092.             trace->surface = &(leadside->surface->c);
  1093.             trace->contents = brush->contents;
  1094.         }
  1095.     }
  1096. }
  1097.  
  1098. /*
  1099. ================
  1100. CM_TestBoxInBrush
  1101. ================
  1102. */
  1103. void CM_TestBoxInBrush (vec3_t mins, vec3_t maxs, vec3_t p1,
  1104.                       trace_t *trace, cbrush_t *brush)
  1105. {
  1106.     int            i, j;
  1107.     cplane_t    *plane;
  1108.     float        dist;
  1109.     vec3_t        ofs;
  1110.     float        d1;
  1111.     cbrushside_t    *side;
  1112.  
  1113.     if (!brush->numsides)
  1114.         return;
  1115.  
  1116.     for (i=0 ; i<brush->numsides ; i++)
  1117.     {
  1118.         side = &map_brushsides[brush->firstbrushside+i];
  1119.         plane = side->plane;
  1120.  
  1121.         // FIXME: special case for axial
  1122.  
  1123.         // general box case
  1124.  
  1125.         // push the plane out apropriately for mins/maxs
  1126.  
  1127.         // FIXME: use signbits into 8 way lookup for each mins/maxs
  1128.         for (j=0 ; j<3 ; j++)
  1129.         {
  1130.             if (plane->normal[j] < 0)
  1131.                 ofs[j] = maxs[j];
  1132.             else
  1133.                 ofs[j] = mins[j];
  1134.         }
  1135.         dist = DotProduct (ofs, plane->normal);
  1136.         dist = plane->dist - dist;
  1137.  
  1138.         d1 = DotProduct (p1, plane->normal) - dist;
  1139.  
  1140.         // if completely in front of face, no intersection
  1141.         if (d1 > 0)
  1142.             return;
  1143.  
  1144.     }
  1145.  
  1146.     // inside this brush
  1147.     trace->startsolid = trace->allsolid = true;
  1148.     trace->fraction = 0;
  1149.     trace->contents = brush->contents;
  1150. }
  1151.  
  1152.  
  1153. /*
  1154. ================
  1155. CM_TraceToLeaf
  1156. ================
  1157. */
  1158. void CM_TraceToLeaf (int leafnum)
  1159. {
  1160.     int            k;
  1161.     int            brushnum;
  1162.     cleaf_t        *leaf;
  1163.     cbrush_t    *b;
  1164.  
  1165.     leaf = &map_leafs[leafnum];
  1166.     if ( !(leaf->contents & trace_contents))
  1167.         return;
  1168.     // trace line against all brushes in the leaf
  1169.     for (k=0 ; k<leaf->numleafbrushes ; k++)
  1170.     {
  1171.         brushnum = map_leafbrushes[leaf->firstleafbrush+k];
  1172.         b = &map_brushes[brushnum];
  1173.         if (b->checkcount == checkcount)
  1174.             continue;    // already checked this brush in another leaf
  1175.         b->checkcount = checkcount;
  1176.  
  1177.         if ( !(b->contents & trace_contents))
  1178.             continue;
  1179.         CM_ClipBoxToBrush (trace_mins, trace_maxs, trace_start, trace_end, &trace_trace, b);
  1180.         if (!trace_trace.fraction)
  1181.             return;
  1182.     }
  1183.  
  1184. }
  1185.  
  1186.  
  1187. /*
  1188. ================
  1189. CM_TestInLeaf
  1190. ================
  1191. */
  1192. void CM_TestInLeaf (int leafnum)
  1193. {
  1194.     int            k;
  1195.     int            brushnum;
  1196.     cleaf_t        *leaf;
  1197.     cbrush_t    *b;
  1198.  
  1199.     leaf = &map_leafs[leafnum];
  1200.     if ( !(leaf->contents & trace_contents))
  1201.         return;
  1202.     // trace line against all brushes in the leaf
  1203.     for (k=0 ; k<leaf->numleafbrushes ; k++)
  1204.     {
  1205.         brushnum = map_leafbrushes[leaf->firstleafbrush+k];
  1206.         b = &map_brushes[brushnum];
  1207.         if (b->checkcount == checkcount)
  1208.             continue;    // already checked this brush in another leaf
  1209.         b->checkcount = checkcount;
  1210.  
  1211.         if ( !(b->contents & trace_contents))
  1212.             continue;
  1213.         CM_TestBoxInBrush (trace_mins, trace_maxs, trace_start, &trace_trace, b);
  1214.         if (!trace_trace.fraction)
  1215.             return;
  1216.     }
  1217.  
  1218. }
  1219.  
  1220.  
  1221. /*
  1222. ==================
  1223. CM_RecursiveHullCheck
  1224.  
  1225. ==================
  1226. */
  1227. void CM_RecursiveHullCheck (int num, float p1f, float p2f, vec3_t p1, vec3_t p2)
  1228. {
  1229.     cnode_t        *node;
  1230.     cplane_t    *plane;
  1231.     float        t1, t2, offset;
  1232.     float        frac, frac2;
  1233.     float        idist;
  1234.     int            i;
  1235.     vec3_t        mid;
  1236.     int            side;
  1237.     float        midf;
  1238.  
  1239.     if (trace_trace.fraction <= p1f)
  1240.         return;        // already hit something nearer
  1241.  
  1242.     // if < 0, we are in a leaf node
  1243.     if (num < 0)
  1244.     {
  1245.         CM_TraceToLeaf (-1-num);
  1246.         return;
  1247.     }
  1248.  
  1249.     //
  1250.     // find the point distances to the seperating plane
  1251.     // and the offset for the size of the box
  1252.     //
  1253.     node = map_nodes + num;
  1254.     plane = node->plane;
  1255.  
  1256.     if (plane->type < 3)
  1257.     {
  1258.         t1 = p1[plane->type] - plane->dist;
  1259.         t2 = p2[plane->type] - plane->dist;
  1260.         offset = trace_extents[plane->type];
  1261.     }
  1262.     else
  1263.     {
  1264.         t1 = DotProduct (plane->normal, p1) - plane->dist;
  1265.         t2 = DotProduct (plane->normal, p2) - plane->dist;
  1266.         if (trace_ispoint)
  1267.             offset = 0;
  1268.         else
  1269.             offset = fabs(trace_extents[0]*plane->normal[0]) +
  1270.                 fabs(trace_extents[1]*plane->normal[1]) +
  1271.                 fabs(trace_extents[2]*plane->normal[2]);
  1272.     }
  1273.  
  1274.  
  1275. #if 0
  1276. CM_RecursiveHullCheck (node->children[0], p1f, p2f, p1, p2);
  1277. CM_RecursiveHullCheck (node->children[1], p1f, p2f, p1, p2);
  1278. return;
  1279. #endif
  1280.  
  1281.     // see which sides we need to consider
  1282.     if (t1 >= offset && t2 >= offset)
  1283.     {
  1284.         CM_RecursiveHullCheck (node->children[0], p1f, p2f, p1, p2);
  1285.         return;
  1286.     }
  1287.     if (t1 < -offset && t2 < -offset)
  1288.     {
  1289.         CM_RecursiveHullCheck (node->children[1], p1f, p2f, p1, p2);
  1290.         return;
  1291.     }
  1292.  
  1293.     // put the crosspoint DIST_EPSILON pixels on the near side
  1294.     if (t1 < t2)
  1295.     {
  1296.         idist = 1.0/(t1-t2);
  1297.         side = 1;
  1298.         frac2 = (t1 + offset + DIST_EPSILON)*idist;
  1299.         frac = (t1 - offset + DIST_EPSILON)*idist;
  1300.     }
  1301.     else if (t1 > t2)
  1302.     {
  1303.         idist = 1.0/(t1-t2);
  1304.         side = 0;
  1305.         frac2 = (t1 - offset - DIST_EPSILON)*idist;
  1306.         frac = (t1 + offset + DIST_EPSILON)*idist;
  1307.     }
  1308.     else
  1309.     {
  1310.         side = 0;
  1311.         frac = 1;
  1312.         frac2 = 0;
  1313.     }
  1314.  
  1315.     // move up to the node
  1316.     if (frac < 0)
  1317.         frac = 0;
  1318.     if (frac > 1)
  1319.         frac = 1;
  1320.         
  1321.     midf = p1f + (p2f - p1f)*frac;
  1322.     for (i=0 ; i<3 ; i++)
  1323.         mid[i] = p1[i] + frac*(p2[i] - p1[i]);
  1324.  
  1325.     CM_RecursiveHullCheck (node->children[side], p1f, midf, p1, mid);
  1326.  
  1327.  
  1328.     // go past the node
  1329.     if (frac2 < 0)
  1330.         frac2 = 0;
  1331.     if (frac2 > 1)
  1332.         frac2 = 1;
  1333.         
  1334.     midf = p1f + (p2f - p1f)*frac2;
  1335.     for (i=0 ; i<3 ; i++)
  1336.         mid[i] = p1[i] + frac2*(p2[i] - p1[i]);
  1337.  
  1338.     CM_RecursiveHullCheck (node->children[side^1], midf, p2f, mid, p2);
  1339. }
  1340.  
  1341.  
  1342.  
  1343. //======================================================================
  1344.  
  1345. /*
  1346. ==================
  1347. CM_BoxTrace
  1348. ==================
  1349. */
  1350. trace_t        CM_BoxTrace (vec3_t start, vec3_t end,
  1351.                           vec3_t mins, vec3_t maxs,
  1352.                           int headnode, int brushmask)
  1353. {
  1354.     int        i;
  1355.  
  1356.     checkcount++;        // for multi-check avoidance
  1357.  
  1358.     c_traces++;            // for statistics, may be zeroed
  1359.  
  1360.     // fill in a default trace
  1361.     memset (&trace_trace, 0, sizeof(trace_trace));
  1362.     trace_trace.fraction = 1;
  1363.     trace_trace.surface = &(nullsurface.c);
  1364.  
  1365.     if (!numnodes)    // map not loaded
  1366.         return trace_trace;
  1367.  
  1368.     trace_contents = brushmask;
  1369.     VectorCopy (start, trace_start);
  1370.     VectorCopy (end, trace_end);
  1371.     VectorCopy (mins, trace_mins);
  1372.     VectorCopy (maxs, trace_maxs);
  1373.  
  1374.     //
  1375.     // check for position test special case
  1376.     //
  1377.     if (start[0] == end[0] && start[1] == end[1] && start[2] == end[2])
  1378.     {
  1379.         int        leafs[1024];
  1380.         int        i, numleafs;
  1381.         vec3_t    c1, c2;
  1382.         int        topnode;
  1383.  
  1384.         VectorAdd (start, mins, c1);
  1385.         VectorAdd (start, maxs, c2);
  1386.         for (i=0 ; i<3 ; i++)
  1387.         {
  1388.             c1[i] -= 1;
  1389.             c2[i] += 1;
  1390.         }
  1391.  
  1392.         numleafs = CM_BoxLeafnums_headnode (c1, c2, leafs, 1024, headnode, &topnode);
  1393.         for (i=0 ; i<numleafs ; i++)
  1394.         {
  1395.             CM_TestInLeaf (leafs[i]);
  1396.             if (trace_trace.allsolid)
  1397.                 break;
  1398.         }
  1399.         VectorCopy (start, trace_trace.endpos);
  1400.         return trace_trace;
  1401.     }
  1402.  
  1403.     //
  1404.     // check for point special case
  1405.     //
  1406.     if (mins[0] == 0 && mins[1] == 0 && mins[2] == 0
  1407.         && maxs[0] == 0 && maxs[1] == 0 && maxs[2] == 0)
  1408.     {
  1409.         trace_ispoint = true;
  1410.         VectorClear (trace_extents);
  1411.     }
  1412.     else
  1413.     {
  1414.         trace_ispoint = false;
  1415.         trace_extents[0] = -mins[0] > maxs[0] ? -mins[0] : maxs[0];
  1416.         trace_extents[1] = -mins[1] > maxs[1] ? -mins[1] : maxs[1];
  1417.         trace_extents[2] = -mins[2] > maxs[2] ? -mins[2] : maxs[2];
  1418.     }
  1419.  
  1420.     //
  1421.     // general sweeping through world
  1422.     //
  1423.     CM_RecursiveHullCheck (headnode, 0, 1, start, end);
  1424.  
  1425.     if (trace_trace.fraction == 1)
  1426.     {
  1427.         VectorCopy (end, trace_trace.endpos);
  1428.     }
  1429.     else
  1430.     {
  1431.         for (i=0 ; i<3 ; i++)
  1432.             trace_trace.endpos[i] = start[i] + trace_trace.fraction * (end[i] - start[i]);
  1433.     }
  1434.     return trace_trace;
  1435. }
  1436.  
  1437.  
  1438. /*
  1439. ==================
  1440. CM_TransformedBoxTrace
  1441.  
  1442. Handles offseting and rotation of the end points for moving and
  1443. rotating entities
  1444. ==================
  1445. */
  1446. #ifdef _WIN32
  1447. #pragma optimize( "", off )
  1448. #endif
  1449.  
  1450.  
  1451. trace_t        CM_TransformedBoxTrace (vec3_t start, vec3_t end,
  1452.                           vec3_t mins, vec3_t maxs,
  1453.                           int headnode, int brushmask,
  1454.                           vec3_t origin, vec3_t angles)
  1455. {
  1456.     trace_t        trace;
  1457.     vec3_t        start_l, end_l;
  1458.     vec3_t        a;
  1459.     vec3_t        forward, right, up;
  1460.     vec3_t        temp;
  1461.     qboolean    rotated;
  1462.  
  1463.     // subtract origin offset
  1464.     VectorSubtract (start, origin, start_l);
  1465.     VectorSubtract (end, origin, end_l);
  1466.  
  1467.     // rotate start and end into the models frame of reference
  1468.     if (headnode != box_headnode && 
  1469.     (angles[0] || angles[1] || angles[2]) )
  1470.         rotated = true;
  1471.     else
  1472.         rotated = false;
  1473.  
  1474.     if (rotated)
  1475.     {
  1476.         AngleVectors (angles, forward, right, up);
  1477.  
  1478.         VectorCopy (start_l, temp);
  1479.         start_l[0] = DotProduct (temp, forward);
  1480.         start_l[1] = -DotProduct (temp, right);
  1481.         start_l[2] = DotProduct (temp, up);
  1482.  
  1483.         VectorCopy (end_l, temp);
  1484.         end_l[0] = DotProduct (temp, forward);
  1485.         end_l[1] = -DotProduct (temp, right);
  1486.         end_l[2] = DotProduct (temp, up);
  1487.     }
  1488.  
  1489.     // sweep the box through the model
  1490.     trace = CM_BoxTrace (start_l, end_l, mins, maxs, headnode, brushmask);
  1491.  
  1492.     if (rotated && trace.fraction != 1.0)
  1493.     {
  1494.         // FIXME: figure out how to do this with existing angles
  1495.         VectorNegate (angles, a);
  1496.         AngleVectors (a, forward, right, up);
  1497.  
  1498.         VectorCopy (trace.plane.normal, temp);
  1499.         trace.plane.normal[0] = DotProduct (temp, forward);
  1500.         trace.plane.normal[1] = -DotProduct (temp, right);
  1501.         trace.plane.normal[2] = DotProduct (temp, up);
  1502.     }
  1503.  
  1504.     trace.endpos[0] = start[0] + trace.fraction * (end[0] - start[0]);
  1505.     trace.endpos[1] = start[1] + trace.fraction * (end[1] - start[1]);
  1506.     trace.endpos[2] = start[2] + trace.fraction * (end[2] - start[2]);
  1507.  
  1508.     return trace;
  1509. }
  1510.  
  1511. #ifdef _WIN32
  1512. #pragma optimize( "", on )
  1513. #endif
  1514.  
  1515.  
  1516.  
  1517. /*
  1518. ===============================================================================
  1519.  
  1520. PVS / PHS
  1521.  
  1522. ===============================================================================
  1523. */
  1524.  
  1525. /*
  1526. ===================
  1527. CM_DecompressVis
  1528. ===================
  1529. */
  1530. void CM_DecompressVis (byte *in, byte *out)
  1531. {
  1532.     int        c;
  1533.     byte    *out_p;
  1534.     int        row;
  1535.  
  1536.     row = (numclusters+7)>>3;    
  1537.     out_p = out;
  1538.  
  1539.     if (!in || !numvisibility)
  1540.     {    // no vis info, so make all visible
  1541.         while (row)
  1542.         {
  1543.             *out_p++ = 0xff;
  1544.             row--;
  1545.         }
  1546.         return;        
  1547.     }
  1548.  
  1549.     do
  1550.     {
  1551.         if (*in)
  1552.         {
  1553.             *out_p++ = *in++;
  1554.             continue;
  1555.         }
  1556.     
  1557.         c = in[1];
  1558.         in += 2;
  1559.         if ((out_p - out) + c > row)
  1560.         {
  1561.             c = row - (out_p - out);
  1562.             Com_DPrintf ("warning: Vis decompression overrun\n");
  1563.         }
  1564.         while (c)
  1565.         {
  1566.             *out_p++ = 0;
  1567.             c--;
  1568.         }
  1569.     } while (out_p - out < row);
  1570. }
  1571.  
  1572. byte    pvsrow[MAX_MAP_LEAFS/8];
  1573. byte    phsrow[MAX_MAP_LEAFS/8];
  1574.  
  1575. byte    *CM_ClusterPVS (int cluster)
  1576. {
  1577.     if (cluster == -1)
  1578.         memset (pvsrow, 0, (numclusters+7)>>3);
  1579.     else
  1580.         CM_DecompressVis (map_visibility + map_vis->bitofs[cluster][DVIS_PVS], pvsrow);
  1581.     return pvsrow;
  1582. }
  1583.  
  1584. byte    *CM_ClusterPHS (int cluster)
  1585. {
  1586.     if (cluster == -1)
  1587.         memset (phsrow, 0, (numclusters+7)>>3);
  1588.     else
  1589.         CM_DecompressVis (map_visibility + map_vis->bitofs[cluster][DVIS_PHS], phsrow);
  1590.     return phsrow;
  1591. }
  1592.  
  1593.  
  1594. /*
  1595. ===============================================================================
  1596.  
  1597. AREAPORTALS
  1598.  
  1599. ===============================================================================
  1600. */
  1601.  
  1602. void FloodArea_r (carea_t *area, int floodnum)
  1603. {
  1604.     int        i;
  1605.     dareaportal_t    *p;
  1606.  
  1607.     if (area->floodvalid == floodvalid)
  1608.     {
  1609.         if (area->floodnum == floodnum)
  1610.             return;
  1611.         Com_Error (ERR_DROP, "FloodArea_r: reflooded");
  1612.     }
  1613.  
  1614.     area->floodnum = floodnum;
  1615.     area->floodvalid = floodvalid;
  1616.     p = &map_areaportals[area->firstareaportal];
  1617.     for (i=0 ; i<area->numareaportals ; i++, p++)
  1618.     {
  1619.         if (portalopen[p->portalnum])
  1620.             FloodArea_r (&map_areas[p->otherarea], floodnum);
  1621.     }
  1622. }
  1623.  
  1624. /*
  1625. ====================
  1626. FloodAreaConnections
  1627.  
  1628.  
  1629. ====================
  1630. */
  1631. void    FloodAreaConnections (void)
  1632. {
  1633.     int        i;
  1634.     carea_t    *area;
  1635.     int        floodnum;
  1636.  
  1637.     // all current floods are now invalid
  1638.     floodvalid++;
  1639.     floodnum = 0;
  1640.  
  1641.     // area 0 is not used
  1642.     for (i=1 ; i<numareas ; i++)
  1643.     {
  1644.         area = &map_areas[i];
  1645.         if (area->floodvalid == floodvalid)
  1646.             continue;        // already flooded into
  1647.         floodnum++;
  1648.         FloodArea_r (area, floodnum);
  1649.     }
  1650.  
  1651. }
  1652.  
  1653. void    CM_SetAreaPortalState (int portalnum, qboolean open)
  1654. {
  1655.     if (portalnum > numareaportals)
  1656.         Com_Error (ERR_DROP, "areaportal > numareaportals");
  1657.  
  1658.     portalopen[portalnum] = open;
  1659.     FloodAreaConnections ();
  1660. }
  1661.  
  1662. qboolean    CM_AreasConnected (int area1, int area2)
  1663. {
  1664.     if (map_noareas->value)
  1665.         return true;
  1666.  
  1667.     if (area1 > numareas || area2 > numareas)
  1668.         Com_Error (ERR_DROP, "area > numareas");
  1669.  
  1670.     if (map_areas[area1].floodnum == map_areas[area2].floodnum)
  1671.         return true;
  1672.     return false;
  1673. }
  1674.  
  1675.  
  1676. /*
  1677. =================
  1678. CM_WriteAreaBits
  1679.  
  1680. Writes a length byte followed by a bit vector of all the areas
  1681. that area in the same flood as the area parameter
  1682.  
  1683. This is used by the client refreshes to cull visibility
  1684. =================
  1685. */
  1686. int CM_WriteAreaBits (byte *buffer, int area)
  1687. {
  1688.     int        i;
  1689.     int        floodnum;
  1690.     int        bytes;
  1691.  
  1692.     bytes = (numareas+7)>>3;
  1693.  
  1694.     if (map_noareas->value)
  1695.     {    // for debugging, send everything
  1696.         memset (buffer, 255, bytes);
  1697.     }
  1698.     else
  1699.     {
  1700.         memset (buffer, 0, bytes);
  1701.  
  1702.         floodnum = map_areas[area].floodnum;
  1703.         for (i=0 ; i<numareas ; i++)
  1704.         {
  1705.             if (map_areas[i].floodnum == floodnum || !area)
  1706.                 buffer[i>>3] |= 1<<(i&7);
  1707.         }
  1708.     }
  1709.  
  1710.     return bytes;
  1711. }
  1712.  
  1713.  
  1714. /*
  1715. ===================
  1716. CM_WritePortalState
  1717.  
  1718. Writes the portal state to a savegame file
  1719. ===================
  1720. */
  1721. void    CM_WritePortalState (FILE *f)
  1722. {
  1723.     fwrite (portalopen, sizeof(portalopen), 1, f);
  1724. }
  1725.  
  1726. /*
  1727. ===================
  1728. CM_ReadPortalState
  1729.  
  1730. Reads the portal state from a savegame file
  1731. and recalculates the area connections
  1732. ===================
  1733. */
  1734. void    CM_ReadPortalState (FILE *f)
  1735. {
  1736.     FS_Read (portalopen, sizeof(portalopen), f);
  1737.     FloodAreaConnections ();
  1738. }
  1739.  
  1740. /*
  1741. =============
  1742. CM_HeadnodeVisible
  1743.  
  1744. Returns true if any leaf under headnode has a cluster that
  1745. is potentially visible
  1746. =============
  1747. */
  1748. qboolean CM_HeadnodeVisible (int nodenum, byte *visbits)
  1749. {
  1750.     int        leafnum;
  1751.     int        cluster;
  1752.     cnode_t    *node;
  1753.  
  1754.     if (nodenum < 0)
  1755.     {
  1756.         leafnum = -1-nodenum;
  1757.         cluster = map_leafs[leafnum].cluster;
  1758.         if (cluster == -1)
  1759.             return false;
  1760.         if (visbits[cluster>>3] & (1<<(cluster&7)))
  1761.             return true;
  1762.         return false;
  1763.     }
  1764.  
  1765.     node = &map_nodes[nodenum];
  1766.     if (CM_HeadnodeVisible(node->children[0], visbits))
  1767.         return true;
  1768.     return CM_HeadnodeVisible(node->children[1], visbits);
  1769. }
  1770.  
  1771.